package buaa.leetcode.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

import buaa.leetcode.utilBeans.TreeLinkNode;
import buaa.leetcode.utilBeans.TreeNode;

public class BinaryTreePreorderTraversal {
	public List<Integer> preorderTraversal(TreeNode root) {
		if(root == null ){}
        List<Integer> list = new ArrayList<Integer>();
        if(root == null ){return list;}
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(!stack.isEmpty() || root != null){
        	while(root != null){
        		list.add(root.val);
        		stack.push(root);
        		root = root.left;
        	}
        	if(!stack.isEmpty()){
        		root = stack.pop();
        		root = root.right;
        	}
        }
        return list;
    }
}
